package _07_串;

import java.util.*;

public class _301_删除无效的括号 {

    public static void main(String[] args) {

        _301_删除无效的括号 v = new _301_删除无效的括号();

        String str = "((";
        List<String> strings = v.removeInvalidParentheses(str);
        System.out.println(strings);
    }

    private List<String> results = new ArrayList<>();

    private Set<String> temp = new HashSet<>();

    public List<String> removeInvalidParentheses(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        // 利用栈消除有效括号剩下无效括号组合
        Stack<int[]> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            char cur = chars[i];
            if (Character.isLetter(cur)) continue;
            if (stack.isEmpty() || stack.peek()[0] != '(' || cur == '(')
                stack.push(new int[]{cur, i});
            else {
                stack.pop();
            }
        }
        int rightBracketIndex = chars.length;
        int rightBracketCount = 0;
        int leftBracketIndex = -1;
        int leftBracketCount = 0;
        // 弹出栈，计算最后一个左括号的索引，第一个右括号的索引
        while (!stack.isEmpty()) {
            int[] ele = stack.pop();
            char pop = (char) ele[0];
            int index = ele[1];
            if (pop == '(') {
                rightBracketCount++;
                rightBracketIndex = index;
            } else {
                leftBracketCount++;
                if (leftBracketIndex == -1) {
                    leftBracketIndex = index;
                }
            }
        }
        if (leftBracketCount == 0 && rightBracketCount == 0) {
            results.add(new String(chars));
            return results;
        }
        int leftEnd = leftBracketIndex == -1 ? rightBracketIndex - 1 : leftBracketIndex;
        int rightEnd = rightBracketIndex == -1 ? leftBracketIndex + 1 : rightBracketIndex;
        int leftStoreIndex = leftEnd - leftBracketCount;
        int rightStoreIndex = leftStoreIndex + 1;

        // 深度遍历左右括号
        dfs(chars, leftBracketIndex, leftBracketCount, leftEnd, leftStoreIndex,
                rightBracketIndex, rightBracketCount, rightEnd, rightStoreIndex,
                new char[len - leftBracketCount - rightBracketCount]);
        return Arrays.asList(temp.toArray(new String[0]));
    }

    private void dfs(char[] chars, int leftBracketIndex, int leftBracketCount, int leftEnd, int leftStoreIndex,
                     int rightBracketIndex, int rightBracketCount, int rightEnd, int rightStoreIndex, char[] list) {
        if (leftBracketCount == 0 && rightBracketCount == 0) {
            for (int i = leftEnd; i >= 0; i--) {
                list[leftStoreIndex--] = chars[i];
            }
            for (int i = rightEnd; i < chars.length; i++) {
                list[rightStoreIndex++] = chars[i];
            }
            temp.add(new String(list));
        } else if (leftBracketCount > 0) {
            for (int i = leftBracketIndex; i >= 0; i--) {
                char cur = chars[i];
                if (cur == ')') {
                    int temp = leftStoreIndex;
                    for (int j = leftEnd; j > i; j--) {
                        list[temp--] = chars[j];
                    }
                    dfs(chars, i - 1, leftBracketCount - 1, i - 1, temp,
                            rightBracketIndex, rightBracketCount, rightEnd, rightStoreIndex, list);
                }
            }
        } else {
            for (int i = rightBracketIndex; i < chars.length; i++) {
                char cur = chars[i];
                if (cur == '(') {
                    int temp = rightStoreIndex;
                    for (int j = rightEnd; j < i; j++) {
                        list[temp++] = chars[j];
                    }
                    dfs(chars, leftBracketIndex, leftBracketCount, leftEnd, leftStoreIndex,
                            i + 1, rightBracketCount - 1, i + 1, temp, list);
                }
            }
        }

    }

}
